package com.ctrip.study.algorithm.pratice;

import org.junit.Test;

import junit.framework.TestCase;

/**
 * 把二元查找树转变成排序的双向链表.
 */
public class TreeToLink extends TestCase {

	@Test
	public void test() {
		Tree tree = constractTree();
		TreeToLink link = new TreeToLink();
		link.toLink(tree);
		
	}

	public void toLink(Tree tree) {
		//如果树为空
		if(tree == null || tree.root == null){
			return;
		}
		link(tree.root);
	}
	
	private void link(Node node) {
		if(isLeaf(node)){
			return;
		}
		if(node.left != null){
			link(node.left);
			Node leftMaxNode = getLeftMaxValue(node.left);
			node.pre = leftMaxNode;
			leftMaxNode.next = node;
		}
		if(node.right != null){
			link(node.right);
			Node rightMinValue = getRightMinValue(node.right);
			node.next = rightMinValue;
			rightMinValue.pre = node;
		}
	}

	/**
	 * 判断节点是否为叶子节点.
	 *
	 * @param node the node
	 * @return true, if is leaf
	 */
	private boolean isLeaf(Node node) {
		return (node.left == null && node.right == null);
	}

	/**
	 * 获取右子树的最小值.
	 *
	 * @param node the node
	 * @return the left max value
	 */
	private Node getRightMinValue(Node node) {
		if(node.left == null){
			return node;
		}
		return getRightMinValue(node.left);
	}

	/**
	 * 获取左子树的最大值.
	 *
	 * @param node the node
	 * @return the left max value
	 */
	private Node getLeftMaxValue(Node node) {
		if(node.right == null){
			return node;
		}
		return getLeftMaxValue(node.right);
	}

	public Tree constractTree() {
		Tree tree = new Tree();
		tree.insert(10);
		tree.insert(6);
		tree.insert(14);
		tree.insert(4);
		tree.insert(8);
		tree.insert(12);
		tree.insert(16);
		return tree;
	}

	private class Node {
		public int key;
		public Node left;
		public Node right;

		public Node pre;
		public Node next;

		public Node(int key) {
			this.key = key;
		}

		@Override
		public String toString() {
			return "Node [key=" + key + "]";
		}

	}

	private class Tree {
		private Node root;

		public void insert(int key) {
			if (root == null) {
				root = new Node(key);
			} else {
				Node current = root;
				Node parent = null;
				Boolean isLeft = true;
				while (current != null) {
					parent = current;
					if (key < current.key) {
						current = current.left;
						isLeft = true;
					} else {
						current = current.right;
						isLeft = false;
					}
				}
				if (isLeft) {
					parent.left = new Node(key);
				} else {
					parent.right = new Node(key);
				}
			}
		}

	}

}
